/*
	scheduler_functions.c

	contains sub-functions for the scheduler and associated system calls

	Author: Aidan Goddard 25/7/13
*/

#include"headers/types.h"
#include"headers/scheduler_tables.h"
#include"headers/bakery_lock.h"

/*
	uint64_t GetCPUTimeStamp(void)

	returns the current CPU time stamp

	not to be used for accurate timing!
*/

uint64_t GetCPUTimeStamp(void)
{
	uint64_t time_stamp = 0;
	uint32_t lower, upper;
	__asm__ __volatile__("rdtsc" : "=a"(lower), "=d"(upper));
	time_stamp = upper;
	time_stamp = (time_stamp << 32) + lower;
	return time_stamp;
}

/*
	uint64_t CreatePID(uint32_t p_index)

	creates and returns a unique process ID from the given PCB index number
*/
uint64_t CreatePID(uint32_t p_index)
{
	uint64_t PID = GetCPUTimeStamp();
	PID = PID << 16;
	p_index = p_index & 0xffff;
	PID = PID + p_index;
	PID = PID & 0x00ffffffffffffff;
	return PID;
}

/*
	uint64_t CreateTID(uint64_t PID, uint32_t t_index)

	creates and returns a unique TID from the given PID and TCB index
*/
uint64_t CreateTID(uint64_t PID, uint32_t t_index)
{
	uint64_t TID = PID << 8;
	t_index = t_index & 0xff;
	TID = TID + t_index;
	return TID;
}

/*
	uint32_t GetPCBp(uint64_t PID)

	returns the PCB index from the given PID
*/
uint32_t GetPCBp(uint64_t PID)
{
	return PID & 0xffff;
}

/*
	uint32_t GetPCBt(uint64_t TID)

	returns the PCB index from the given TID
*/
uint32_t GetPCBt(uint64_t TID)
{
	return (TID >> 8) & 0xffff;
}

/*
	uint32_t GetTCBt(uint64_t TID)

	returns the TCB index from the given TID
*/
uint32_t GetTCBt(uint64_t TID)
{
	return TID & 0xff;
}

/*
	uint32_t GetCPUID(void)

	returns the OS-assigned CPU number for this CPU
*/
uint32_t GetCPUID(void)
{
	uint64_t CPUID = 0;

	__asm__ __volatile__("str %%rax; movq %%rax, %0":"=r"(CPUID)::"%rax", "memory");
	CPUID = CPUID - 0x40;
	CPUID = CPUID / 0x10;

	return CPUID;
}

/*
	function to get the current TID

	MUST BE CALLED WITH INTERRUPTS DISABLED
*/
uint64_t GetCurrentTID(void)
{
	// get the current CPU ID
	int CPU = GetCPUID();

	// get the current thread PID and TID
	int PID = SCHEDULER->CPU_current_thread[CPU]->PCB_index;
	int TID = SCHEDULER->CPU_current_thread[CPU]->TCB_index;

	// get the TID
	uint64_t to_return = SCHEDULER->PCB[PID].TCB[TID].TID;

	return to_return;
}

/*
	uint32_t MoveThreadToCPU(int CPU, SCH_TLC* thread)

	moves the given thread to the given CPU (it is assumed the given thread is not in any other queue)
	and sets it's state to active
	returns the new count of threads on that CPU

	ASSUMES INTERRUPTS ARE OFF
*/
uint32_t MoveThreadToCPU(int CPU, SCH_TLC* thread)
{
	// get lock on CPU active queue
	int this_cpu = GetCPUID();
	int thread_count = 0;
	BakeryEnter(&(SCHEDULER->CPU_active_lock[CPU]), this_cpu);

	// set this thread's state to normal
	int Pindex = thread->PCB_index;
	int Tindex = thread->TCB_index;
	SCHEDULER->PCB[Pindex].PDB->thread_usage_map[Tindex] = THREAD_STATE_ACTIVE;

	// check the start of this queue to see if it is empty
	if(SCHEDULER->CPU_active_start[CPU] == NULL)
	{
		// queue is empty, put this thread in it and update thread count
		thread_count = 1;
		SCHEDULER->CPU_active_thread_count[CPU] = 1;
		SCHEDULER->CPU_active_start[CPU] = thread;
		SCHEDULER->CPU_active_end[CPU] = thread;
		thread->next_TLC = NULL;
	}
	else
	{
		// queue is not empty
		// update the last object in queue and end of queue pointer
		SCHEDULER->CPU_active_end[CPU]->next_TLC = thread;
		SCHEDULER->CPU_active_end[CPU] = thread;
		thread->next_TLC = NULL;
		thread_count = SCHEDULER->CPU_active_thread_count[CPU] + 1;
		SCHEDULER->CPU_active_thread_count[CPU]++;
	}

	// release lock on queue
	BakeryLeave(&(SCHEDULER->CPU_active_lock[CPU]), this_cpu);

	// finished, return CPU's active thread count
	return thread_count;
}


/*
	function to send the calling thread to sleep for a given amount of micro-seconds

	uint32_t 	SleepMe(uint32_t sleep_time);

	where sleep_time is between 1000 and 2,000,000,000 (2,000 seconds) - the value is clamped if it falls outside of this range

	returns 0 when the thread has been sucessfully sent to sleep for the given time

	note that the system cannot guarantee that the thread will be asleep for the exact given time
*/

#define SLEEPME_RETURN_NORMAL 0

uint64_t SleepMe(uint32_t sleep_time)
{
	// first check the sleep_time is within the constraints
	if(sleep_time > 2000000000)
		sleep_time = 2000000000;
	if(sleep_time < 1000)
		sleep_time = 1000;

	// get the CPU ID
	__asm__ __volatile__("":::"memory");
	__asm__ __volatile__("cli");
	__asm__ __volatile__("":::"memory");
	int CPU = GetCPUID();

	// get the Thread index and the Process index
	int Pindex = SCHEDULER->CPU_current_thread[CPU]->PCB_index;
	int Tindex = SCHEDULER->CPU_current_thread[CPU]->TCB_index;

	// zero the wait return value
	SCHEDULER->PCB[Pindex].TCB[Tindex].wait_return_value = 0;

	// disable interrupts and get a lock on the PCB for this thread
	BakeryEnter(&(SCHEDULER->PCB[Pindex].lock), GetCPUID());

	// check the current thread state
	if(SCHEDULER->PCB[Pindex].PDB->thread_usage_map[Tindex] != THREAD_STATE_TERMINATING)
	{
		// send thread to sleep
		SCHEDULER->PCB[Pindex].PDB->thread_usage_map[Tindex] = THREAD_STATE_SLEEPING;
		SCHEDULER->PCB[Pindex].TCB[Tindex].sleep_counter = sleep_time;
	}

	// release lock
	BakeryLeave(&(SCHEDULER->PCB[Pindex].lock), GetCPUID());

	// yield timeslice (this will play havock with the idle counter, but that's only an approximation, anyway...)
	__asm__ __volatile__("":::"memory");
	__asm__ __volatile__("int $50");
	__asm__ __volatile__("":::"memory");

	// enable interrupts
	__asm__ __volatile__("":::"memory");
	__asm__ __volatile__("sti");
	__asm__ __volatile__("":::"memory");

	// get the return value
	uint64_t to_return = SCHEDULER->PCB[Pindex].TCB[Tindex].wait_return_value;
	return to_return;
}


/*
	function to select the CPU with the lowest count of active threads.

	returns the CPU ID of the selected CPU.
*/

uint32_t GetCPUWithSmallestActiveQueue()
{
	// check each active CPU to find one with lowest active thread count
	// start with CPU x (as CPU 0 is usually reserved for IRQ processing) the monitor process may move it, anyway.
	int active_cpus = SCHEDULER->active_CPU_count;
	int lowest_cpu = SCHEDULER->CPU_selection_start;
	uint32_t lowest_count = 0xffff;
	int i;
	for(i = lowest_cpu; i < active_cpus; i++)
	{
		uint32_t k = SCHEDULER->CPU_active_thread_count[i];
		if(k < lowest_count)
		{
			lowest_count = k;
			lowest_cpu = i;
		}
		if(lowest_count == 0)
		{
			break;
		}
	}

	return lowest_cpu;
}


/*
	function to make the calling thread wait indefinitely

	make sure the calling thread is associated with an EVENT before calling this,
	otherwise it will be stuck in the waiting queue until it is force-terminated.

	returns a custom return value (dictated by the waking event).
*/

uint64_t WaitMe()
{
	// get CPU ID
	__asm__ __volatile__("":::"memory");
	__asm__ __volatile__("cli");
	__asm__ __volatile__("":::"memory");
	int CPU = GetCPUID();

	// get the Thread index and the Process index
	int Pindex = SCHEDULER->CPU_current_thread[CPU]->PCB_index;
	int Tindex = SCHEDULER->CPU_current_thread[CPU]->TCB_index;

	// disable interrupts and get a lock on the PCB for this thread
	BakeryEnter(&(SCHEDULER->PCB[Pindex].lock), GetCPUID());

	// check the current thread state
	if(SCHEDULER->PCB[Pindex].PDB->thread_usage_map[Tindex] != THREAD_STATE_TERMINATING)
	{
		// make thread wait
		SCHEDULER->PCB[Pindex].PDB->thread_usage_map[Tindex] = THREAD_STATE_WAITING;
	}

	// release lock
	BakeryLeave(&(SCHEDULER->PCB[Pindex].lock), GetCPUID());

	// yield timeslice (this will play havock with the idle counter, but that's only an approximation, anyway...)
	__asm__ __volatile__("":::"memory");
	__asm__ __volatile__("int $50");
	__asm__ __volatile__("":::"memory");

	// enable interrupts
	__asm__ __volatile__("":::"memory");
	__asm__ __volatile__("sti");
	__asm__ __volatile__("":::"memory");

	// get the return value
	uint64_t to_return = SCHEDULER->PCB[Pindex].TCB[Tindex].wait_return_value;
	return to_return;
}

/*
	function to wake a waiting or sleeping thread

	the message passed to this function is passed as the return value when the woken thread returns from
	its sleep/wait function call

	returns 0 on success, 1 on failure (thread was not waiting or sleeping)

	MUST BE CALLED WITH INTERRUPTS DISABLED
*/

#define WAKE_THREAD_SUCCESS 0
#define WAKE_THREAD_NOT_SLEEPING 1

uint32_t WakeThread(uint64_t TID, uint64_t message)
{
	// get the TID's Pindex and Tindex
	int Pindex = GetPCBt(TID);
	int Tindex = GetTCBt(TID);

	// define a pointer to the thread
	SCH_TLC *thread = NULL;

	// search through waiting queue
	// get a lock on the waiting queue
	BakeryEnter(&(SCHEDULER->waiting_lock), GetCPUID());

	// check if empty
	if(SCHEDULER->waiting_start != NULL)
	{
		// queue is not empty
		// check the first entry
		int p = SCHEDULER->waiting_start->PCB_index;
		int t = SCHEDULER->waiting_start->TCB_index;
		if((p == Pindex) && (t == Tindex) && ((TID >> 8) == SCHEDULER->PCB[Pindex].PID))
		{
			// Pindex, Tindex and global PID matches. found the thread
			thread = SCHEDULER->waiting_start;
			SCHEDULER->PCB[Pindex].TCB[Tindex].wait_return_value = message;
			SCHEDULER->waiting_start = thread->next_TLC;
			thread->next_TLC = NULL;

			// check if queue is now empty
			if(SCHEDULER->waiting_start == NULL)
			{
				// queue is empty, update end pointer
				SCHEDULER->waiting_end = NULL;
			}
		}
		else
		{
			// it was not the first item
			SCH_TLC *prev_thread = SCHEDULER->waiting_start;

			// iterate through until the thread is found or the end of the queue is found
			while(1)
			{
				// check for end of queue
				if(prev_thread->next_TLC == NULL)
				{
					// reached end of list
					break;
				}

				// check next thread values
				int p = prev_thread->next_TLC->PCB_index;
				int t = prev_thread->next_TLC->TCB_index;
				if((p == Pindex) && (t == Tindex) && ((TID >> 8) == SCHEDULER->PCB[Pindex].PID))
				{
					// Pindex, Tindex and global PID matches. found the thread
					thread = prev_thread->next_TLC;
					SCHEDULER->PCB[Pindex].TCB[Tindex].wait_return_value = message;
					prev_thread->next_TLC = thread->next_TLC;
					if(thread->next_TLC == NULL)
					{
						SCHEDULER->waiting_end = prev_thread;
					}
					thread->next_TLC = NULL;

					break;
				}

				// not this thread, get next one
				prev_thread = prev_thread->next_TLC;
			}
		}

	}

	// release lock
	BakeryLeave(&(SCHEDULER->waiting_lock), GetCPUID());


	// check if the thread was found in the waiting queue
	if(thread == NULL)
	{
		// search through sleeping queue
		// get a lock on the sleeping queue
		BakeryEnter(&(SCHEDULER->sleeping_lock), GetCPUID());

		// check if empty
		if(SCHEDULER->sleeping_start != NULL)
		{
			// queue is not empty
			// check the first entry
			int p = SCHEDULER->sleeping_start->PCB_index;
			int t = SCHEDULER->sleeping_start->TCB_index;
			if((p == Pindex) && (t == Tindex) && ((TID >> 8) == SCHEDULER->PCB[Pindex].PID))
			{
				// Pindex, Tindex and global PID matches. found the thread
				thread = SCHEDULER->sleeping_start;
				SCHEDULER->PCB[Pindex].TCB[Tindex].wait_return_value = message;
				SCHEDULER->sleeping_start = thread->next_TLC;
				SCHEDULER->sleeping_start->sleep_offset += thread->sleep_offset;
				thread->next_TLC = NULL;

				// check if queue is now empty
				if(SCHEDULER->sleeping_start == NULL)
				{
					// queue is empty, update end pointer
					SCHEDULER->sleeping_end = NULL;
				}
			}
			else
			{
				// it was not the first item
				SCH_TLC *prev_thread = SCHEDULER->sleeping_start;

				// iterate through until the thread is found or the end of the queue is found
				while(1)
				{
					// check for end of queue
					if(prev_thread->next_TLC == NULL)
					{
						// reached end of list
						break;
					}

					// check next thread values
					int p = prev_thread->next_TLC->PCB_index;
					int t = prev_thread->next_TLC->TCB_index;
					if((p == Pindex) && (t == Tindex) && ((TID >> 8) == SCHEDULER->PCB[Pindex].PID))
					{
						// Pindex, Tindex and global PID matches. found the thread
						thread = prev_thread->next_TLC;
						SCHEDULER->PCB[Pindex].TCB[Tindex].wait_return_value = message;
						prev_thread->next_TLC = thread->next_TLC;
						prev_thread->next_TLC->sleep_offset += thread->sleep_offset;
						if(thread->next_TLC == NULL)
						{
							SCHEDULER->sleeping_end = prev_thread;
						}
						thread->next_TLC = NULL;

						break;
					}

					// not this thread, get next one
					prev_thread = prev_thread->next_TLC;
				}
			}
		}

		// release lock
		BakeryLeave(&(SCHEDULER->sleeping_lock), GetCPUID());
	}

	// check if thread was found
	if(thread == NULL)
	{
		// thread was not found
		// return error
		return WAKE_THREAD_NOT_SLEEPING;
	}

	// thread was found, move it to a CPU and return success
	int cpu = GetCPUWithSmallestActiveQueue();
	MoveThreadToCPU(cpu, thread);
	return WAKE_THREAD_SUCCESS;
}

/*
	function to kill an active/sleeping/waiting thread

	MUST BE CALLED WITH INTERRUPTS DISABLED
*/

#define KILL_THREAD_SUCCESS 0
#define KILL_THREAD_NOT_ALIVE 1
#define KILL_THREAD_NOT_IN_PROC 2

uint32_t KillThread(uint64_t TID, uint64_t message)
{
	// get thread index and process index
	int tindex = GetTCBt(TID);
	int pindex = GetPCBt(TID);

	// get the current CPU ID
	int CPU = GetCPUID();

	// get a lock on the PCB
	BakeryEnter(&(SCHEDULER->PCB[pindex].lock), CPU);

	// set the return message
	SCHEDULER->PCB[pindex].TCB[tindex].close_return_value = message;

	// check if it's currently sleeping/waiting
	int current_state = SCHEDULER->PCB[pindex].PDB->thread_usage_map[tindex];

	// create the return value
	int to_return = KILL_THREAD_NOT_ALIVE;

	// check if the thread is not already dead/terminating
	if(current_state != THREAD_STATE_INACTIVE)
	{
		// set the thread's state to terminating
		SCHEDULER->PCB[pindex].PDB->thread_usage_map[tindex] = THREAD_STATE_TERMINATING;

		// check its previous state
		if((current_state == THREAD_STATE_SLEEPING) || (current_state == THREAD_STATE_WAITING))
		{
			// wake the thread
			WakeThread(TID, 0);
			SCHEDULER->PCB[pindex].PDB->thread_usage_map[tindex] = THREAD_STATE_TERMINATING;
		}

		// return success
		to_return = KILL_THREAD_SUCCESS;

	}
	// release lock
	BakeryLeave(&(SCHEDULER->PCB[pindex].lock), CPU);

	// finished, return
	return to_return;

}





/*
	function to return the % utilisation of the requested CPU

	requested CPU should be between 0 and 31
*/

uint32_t GetCPUUsage(int CPU)
{
	__asm__ __volatile__("":::"memory");
	__asm__ __volatile__("cli");
	__asm__ __volatile__("":::"memory");

	if(CPU > 31)
		return 0xffffffff;
	if(CPU < 0)
		return 0xffffffff;

	int to_return = SCHEDULER->CPU_pc_usage_final[CPU];
	__asm__ __volatile__("":::"memory");
	__asm__ __volatile__("sti");
	__asm__ __volatile__("":::"memory");

	return to_return;
}

/*
	function to return the number of active threads for the requested CPU
*/

uint32_t GetCPUActiveThreads(int CPU)
{
	__asm__ __volatile__("":::"memory");
	__asm__ __volatile__("cli");
	__asm__ __volatile__("":::"memory");

	if(CPU > 31)
		return 0xffffffff;
	if(CPU < 0)
		return 0xffffffff;

	int to_return = SCHEDULER->CPU_active_thread_count[CPU];
	__asm__ __volatile__("":::"memory");
	__asm__ __volatile__("sti");
	__asm__ __volatile__("":::"memory");

	return to_return;
}

// function to wake an external thread (thread that may not belong to the calling process - ONLY WORKS WITH PCB IN KERNEL UPDATE)
// returns 0 on success, 1 on failure (thread was not waiting or sleeping)
// ASSUMES INTERRUPTS ARE DISABLED
uint32_t WakeThreadEx(uint64_t TID)
{
	// get the TID's Pindex and Tindex
	int Pindex = GetPCBt(TID);
	int Tindex = GetTCBt(TID);

	// define a pointer to the thread
	SCH_TLC *thread = NULL;

	// search through waiting queue
	// get a lock on the waiting queue
	BakeryEnter(&(SCHEDULER->waiting_lock), GetCPUID());

	// check if empty
	if(SCHEDULER->waiting_start != NULL)
	{
		// queue is not empty
		// check the first entry
		int p = SCHEDULER->waiting_start->PCB_index;
		int t = SCHEDULER->waiting_start->TCB_index;
		if((p == Pindex) && (t == Tindex) && ((TID >> 8) == SCHEDULER->PCB[Pindex].PID))
		{
			// Pindex, Tindex and global PID matches. found the thread
			thread = SCHEDULER->waiting_start;
			SCHEDULER->waiting_start = thread->next_TLC;
			thread->next_TLC = NULL;

			// check if queue is now empty
			if(SCHEDULER->waiting_start == NULL)
			{
				// queue is empty, update end pointer
				SCHEDULER->waiting_end = NULL;
			}
		}
		else
		{
			// it was not the first item
			SCH_TLC *prev_thread = SCHEDULER->waiting_start;

			// iterate through until the thread is found or the end of the queue is found
			while(1)
			{
				// check for end of queue
				if(prev_thread->next_TLC == NULL)
				{
					// reached end of list
					break;
				}

				// check next thread values
				int p = prev_thread->next_TLC->PCB_index;
				int t = prev_thread->next_TLC->TCB_index;
				if((p == Pindex) && (t == Tindex) && ((TID >> 8) == SCHEDULER->PCB[Pindex].PID))
				{
					// Pindex, Tindex and global PID matches. found the thread
					thread = prev_thread->next_TLC;
					prev_thread->next_TLC = thread->next_TLC;
					if(thread->next_TLC == NULL)
					{
						SCHEDULER->waiting_end = prev_thread;
					}
					thread->next_TLC = NULL;

					break;
				}

				// not this thread, get next one
				prev_thread = prev_thread->next_TLC;
			}
		}

	}

	// release lock
	BakeryLeave(&(SCHEDULER->waiting_lock), GetCPUID());


	// check if the thread was found in the waiting queue
	if(thread == NULL)
	{
		// search through sleeping queue
		// get a lock on the sleeping queue
		BakeryEnter(&(SCHEDULER->sleeping_lock), GetCPUID());

		// check if empty
		if(SCHEDULER->sleeping_start != NULL)
		{
			// queue is not empty
			// check the first entry
			int p = SCHEDULER->sleeping_start->PCB_index;
			int t = SCHEDULER->sleeping_start->TCB_index;
			if((p == Pindex) && (t == Tindex) && ((TID >> 8) == SCHEDULER->PCB[Pindex].PID))
			{
				// Pindex, Tindex and global PID matches. found the thread
				thread = SCHEDULER->sleeping_start;
				SCHEDULER->sleeping_start = thread->next_TLC;
				SCHEDULER->sleeping_start->sleep_offset += thread->sleep_offset;
				thread->next_TLC = NULL;

				// check if queue is now empty
				if(SCHEDULER->sleeping_start == NULL)
				{
					// queue is empty, update end pointer
					SCHEDULER->sleeping_end = NULL;
				}
			}
			else
			{
				// it was not the first item
				SCH_TLC *prev_thread = SCHEDULER->sleeping_start;

				// iterate through until the thread is found or the end of the queue is found
				while(1)
				{
					// check for end of queue
					if(prev_thread->next_TLC == NULL)
					{
						// reached end of list
						break;
					}

					// check next thread values
					int p = prev_thread->next_TLC->PCB_index;
					int t = prev_thread->next_TLC->TCB_index;
					if((p == Pindex) && (t == Tindex) && ((TID >> 8) == SCHEDULER->PCB[Pindex].PID))
					{
						// Pindex, Tindex and global PID matches. found the thread
						thread = prev_thread->next_TLC;
						prev_thread->next_TLC = thread->next_TLC;
						prev_thread->next_TLC->sleep_offset += thread->sleep_offset;
						if(thread->next_TLC == NULL)
						{
							SCHEDULER->sleeping_end = prev_thread;
						}
						thread->next_TLC = NULL;

						break;
					}

					// not this thread, get next one
					prev_thread = prev_thread->next_TLC;
				}
			}
		}

		// release lock
		BakeryLeave(&(SCHEDULER->sleeping_lock), GetCPUID());
	}

	// check if thread was found
	if(thread == NULL)
	{
		// thread was not found
		// return error
		return WAKE_THREAD_NOT_SLEEPING;
	}

	// thread was found, move it to a CPU and return success
	int cpu = GetCPUWithSmallestActiveQueue();
	MoveThreadToCPU(cpu, thread);
	return WAKE_THREAD_SUCCESS;
}





